package cn.easysan.algorithm.tree;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 13545
 * @Description: 二叉树
 * @date 2021/11/1 22:40
 */
public class BinaryTree<Key extends Comparable<Key>, Value> {

    /**
     * 记录根节点
     */
    private Node root;

    /**
     * 记录树中元素的个数
     */
    private int N;

    private class Node{
        /**
         * 存储键
         */
        public Key key;
        /**
         * 存储值
         */
        public Value value;
        /**
         * 记录左子节点
         */
        public Node left;
        /**
         * 记录右子节点
         */
        public Node right;

        public Node(Key key, Value value, Node left, Node right){
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 获取树中元素的个数
     * @return
     */
    public int size(){
        return N;
    }

    /**
     * 向树中添加元素key-value
     * @param key
     * @param value
     */
    public void put(Key key, Value value){
        root = put(root, key, value);
    }

    /**
     * 向指定的树X中添加key-value,并返回添加元素后新的树
     * @param x
     * @param key
     * @param value
     * @return
     */
    private Node put(Node x, Key key, Value value){
        //如果x为空，说明根节点不存在，根据key-value生成根节点
        if(x == null){
            N++;
            return new Node(key, value, null, null);
        }
        //如果x不为空，比较x节点的键和key的大小
        int cmp = key.compareTo(x.key);
        if(cmp > 0){
            //如果key大于x节点的键，则继续找x节点的右子树
            x.right = put(x.right, key, value);
        }else if(cmp < 0){
            //如果key小于x节点的键，则继续找x节点的左子树，如果左子树为空，则将创建出来的节点作为左子树
            x.left = put(x.left, key, value);
        }else{
            //如果key等于x节点的键，则替换x节点的值为value即可
            x.value = value;
        }
        return x;
    }

    /**
     * 查询树中指定的key对应的value
     * @param key
     * @return
     */
    public Value get(Key key){
        return get(root, key);
    }

    /**
     * 从指定的树X中，查找key对应的值
     * @param x
     * @param key
     * @return
     */
    public Value get(Node x, Key key){
        //x 树为null
        if(x == null){
            return null;
        }
        //如果x 树不为null，比较x节点的键和key的大小
        int cmp = key.compareTo(x.key);
        if(cmp > 0){
            //如果key大于x节点的键，则继续找x节点的右子树
            return get(x.right, key);
        }else if(cmp < 0){
            //如果key小于x节点的键，则继续找x节点的左子树，如果左子树为空，则将创建出来的节点作为左子树
            return get(x.left, key);
        }else{
            //如果key等于x节点的键，就找到了键为key的节点，只需返回value
            return x.value;
        }
    }

    /**
     * 删除树中的key对应的value
     * @param key
     */
    public void delete(Key key){
        delete(root, key);
    }

    /**
     * 删除指定树x中的key对应的value,并返回删除后的新树
     * @param x
     * @param key
     * @return
     */
    public Node delete(Node x, Key key){
        //x树为null
        if(x == null){
            return null;
        }
        //x树不为null
        int cmp = key.compareTo(x.key);
        if(cmp > 0){
            //如果key大于x节点的键，则继续找x节点的右子树
            x.right = delete(x.right, key);
        }else if(cmp < 0){
            //如果key小于x节点的键，则继续找x节点的左子树，如果左子树为空，则将创建出来的节点作为左子树
            x.left = delete(x.left, key);
        }else{
            //元素个数减一
            N--;
            //如果key等于x节点的键，就找到了键为key的节点，完成真正的删除节点动作，要删除的节点就是x
            //找到x子树的右子树中的最小的节点
            if(x.right == null){
                return x.left;
            }
            if(x.left == null){
                return x.right;
            }
            //如果左右子树都是存在的,找到当前节点x右子树中的最小键的节点
            Node minNode = x.right;
            while (minNode.left != null){
                minNode = minNode.left;
            }
            //删除右子树中键值最小的节点
            Node n = x.right;
            while (n.left != null){
                if(n.left.left == null){
                    n.left = null;
                }else{
                    //向下变换节点
                    n = n.left;
                }
            }
            //让x节点的左子树成为minNode的左子树
            minNode.left = x.left;
            //让x节点的右子树成为minNode的右子树
            minNode.right = x.right;
            //让x节点的父节点指向minNode
            x = minNode;
        }
        return x;
    }

    /**
     * 查找整个树中最小的键
     * @return
     */
    public Key min(){
        return min(root).key;
    }

    /**
     * 在指定树x中找出最小键所在的节点
     * @param x
     * @return
     */
    public Node min(Node x){
        if(x.left != null){
            return min(x.left);
        }else{
            return x;
        }
    }

    /**
     * 找出整个树中的最大的键
     * @return
     */
    public Key max(){
        return max(root).key;
    }

    /**
     * 找出指定树x中最大值键所在的节点
     * @param x
     * @return
     */
    public Node max(Node x){
        if(x.right != null){
            return max(x.right);
        }else{
            return x;
        }
    }

    /**
     * 前序遍历--获取整个树中所有的键
     * @return
     */
    public List<Key> preErgodic(){
        List<Key> keys = new ArrayList<Key>();
        preErgodic(root, keys);
        return keys;
    }

    /**
     * 前序遍历--获取指定的树x的所有键，并放到keys队列中
     * @param x
     * @param keys
     */
    public void preErgodic(Node x, List<Key> keys){
        if(x == null){
            return ;
        }
        //把x节点的key放入到keys中
        keys.add(x.key);
        //递归遍历x节点的左子树
        if(x.left != null){
            preErgodic(x.left, keys);
        }
        //递归遍历x节点的右子树
        if(x.right != null){
            preErgodic(x.right, keys);
        }
    }

    /**
     * 中序遍历--获取整个树中所有的键
     * @return
     */
    public List<Key> midPreErgodic(){
        List<Key> keys = new ArrayList<Key>();
        midPreErgodic(root, keys);
        return keys;
    }

    /**
     * 中序遍历--获取指定的树x的所有键，并放到keys队列中
     * @param x
     * @param keys
     */
    public void midPreErgodic(Node x, List<Key> keys){
        if(x == null){
            return ;
        }
        //先递归，把左子树中的键放到keys中
        if(x.left != null){
            midPreErgodic(x.left, keys);
        }
        //把当前节点x的键放到keys中
        keys.add(x.key);
        //在递归，把右子树中的键放到keys中
        if(x.right != null){
            midPreErgodic(x.right, keys);
        }
    }

    /**
     * 后序遍历--获取整个树中所有的键
     * @return
     */
    public List<Key> afterPreErgodic(){
        List<Key> keys = new ArrayList<Key>();
        afterPreErgodic(root, keys);
        return keys;
    }

    /**
     * 后序遍历--获取指定的树x的所有键，并放到keys队列中
     * @param x
     * @param keys
     */
    public void afterPreErgodic(Node x, List<Key> keys){
        if(x == null){
            return ;
        }
        //先递归，把左子树中的键放到keys中
        if(x.left != null){
            afterPreErgodic(x.left, keys);
        }
        //在递归，把右子树中的键放到keys中
        if(x.right != null){
            afterPreErgodic(x.right, keys);
        }
        //把当前节点x的键放到keys中
        keys.add(x.key);
    }

    /**
     * 使用层序遍历，获取整个树中的所有的键
     * @return
     */
    public ArrayQueue layerErgodic(){
        //定义两个队列，分别存储树中的键和树中的节点
        ArrayQueue<Key> keys = new ArrayQueue<Key>(10);
        ArrayQueue<Node> nodes = new ArrayQueue<Node>(10);
        //默认，往队列中放入根节点
        nodes.add(root);
        /*while (!nodes.isEmpty()){
            //从队列中弹出一个节点，把key放入到keys中
            Node node = nodes.remove(0);
            keys.add(node.key);
            //判断当前节点还有没有左子节点，如果有，则放入到nodes中
            if(node.left != null){
                nodes.add(node.left);
            }
            //判断当前节点还有没有右子节点，如果有，则放入到nodes中
            if(node.right != null){
                nodes.add(node.right);
            }
        }*/
        layerErgodic(keys, nodes);
        return keys;
    }

    /**
     * 使用层序遍历，获取指定树中的所有的键
     * @param keys
     * @param nodes
     */
    public void layerErgodic(ArrayQueue<Key> keys, ArrayQueue<Node> nodes){
        //当存放节点的队列为空时，层序遍历完成
        if(nodes.isEmpty()){
            return ;
        }
        //从队列中弹出一个节点，把key放入到keys中
        Node node = nodes.remove(0);
        keys.add(node.key);
        //判断当前节点还有没有左子节点，如果有，则放入到nodes中
        if(node.left != null){
            nodes.add(node.left);
        }
        //判断当前节点还有没有右子节点，如果有，则放入到nodes中
        if(node.right != null){
            nodes.add(node.right);
        }
        layerErgodic(keys, nodes);
    }

    /**
     * 获取整个树的最大深度
     * @return
     */
    public int maxDepth(){
        return maxDepth(root);
    }

    /**
     * 获取指定树x的最大深度
     * 使用了递归可以返回的特性，先一直往下走到头，在利用递归可以返回的特性，计算递归的次数，改次数就相当于层数。
     * 不过次数分为左边和右边，故需要比较左右大小，取最大
     * @param x
     * @return
     */
    private int maxDepth(Node x){
        if(x == null){
            return 0;
        }
        //x的最大深度
        int max = 0;
        //左子树的最大深度
        int maxL = 0;
        //右子树的最大深度
        int maxR = 0;
        //计算x节点左子树的最大深度
        if(x.left != null){
            maxL = maxDepth(x.left);
        }
        //计算x节点右子树的最大深度
        if(x.right != null){
            maxR = maxDepth(x.right);
        }
        //比较左子树最大深度和右子树的最大深度，取较大的值加1即可
        max = maxL>maxR ? maxL+1 : maxR+1;
        return max;
    }
}
